package 力扣.动态规划.区间DP.背包问题;

import java.util.Scanner;

public class _01背包问题 {
    //测试地址：https://www.acwing.com/problem/content/2/
    static private _01背包问题 s = new _01背包问题();

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 背包的数目
            int N = sc.nextInt();
            if (N <= 0) {
                break;
            }
            // 容量
            int V = sc.nextInt();

            int[] v = new int[N];
            int[] w = new int[N];
            // 读入每个背包
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();//体积
                w[i] = sc.nextInt();//价值
            }

            System.out.println(s.Solve(N, V, v, w));
        }
}

    private int Solve(int N, int V, int[] v, int[] w) {
        if (N == 0 || V == 0){
            return 0;
        }
        int[] dp = new int[V + 1];//当前背包容量为x时，所能装的最大容量
        /**
         *  dp[x]:当前已经使用容量为x时，背包内物品的最大价值
         *  刚开始的点集为s[0,V],我们不断地进行更新点集中的元素（这里更新的是价值）,逆序
         *  递推关系式：dp[x] = Max(dp[x - v[i] + w[i]],dp[x]);
         *  注意：因为是减法，为了防止数组溢出，这里要从v[i]开始更新，即[v[i],V]
         *  为什么逆序？
         *    如果是正序，在更新点集时，我们会使用多次v[i]
         *    如果是逆序，因为都是正整数，所以可以保证只使用一次v[i]
         */
        for (int i = 0; i < N; i++) {
            //更新旧的点集，注意遍历的方向
            for (int j = V; j >= v[i]; j--) {//保证只使用一次v[i]
                int preSpace = j - v[i];
                int thisSpace = j;
                dp[thisSpace] = Math.max(dp[thisSpace],dp[preSpace] + w[i]);
            }
        }
        return dp[V];
    }



    private int Solve2(int N ,int V ,int[] v,int[] w){
        if (N == 0 || V == 0){
            return 0;
        }
        int[] dp = new int[V + 1];
        for (int i = 0; i < N; i++) {//不断更新点集
            for (int j = V; j >= v[i] ; j--) {
               dp[j] = Math.max((dp[j - v[i]] + w[i]),dp[j]);
            }
        }
        return dp[V];
    }
}
